package leetcode.editor.cn;

import java.util.*;

public class _347_TopKFrequentElements {
    public static void main(String[] args) {
        Solution solution = new _347_TopKFrequentElements().new Solution();
        int[] nums = {1, 1, 1, 2, 2, 3};
        int[] ints = solution.topKFrequent(nums, 2);
        System.out.println(Arrays.toString(ints));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // 小顶堆
    class Solution1 {
        public int[] topKFrequent(int[] nums, int k) {
            int[] res = new int[k];
            Map<Integer, Integer> map = new HashMap<>();
            for (int num : nums) {
                map.put(num, map.getOrDefault(num, 0) + 1);
            }
            PriorityQueue<int[]> heap = new PriorityQueue<>(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[1] - o2[1];
                }
            });
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                int key = entry.getKey(), value = entry.getValue();
                if (heap.size() == k) {
                    if (value > heap.peek()[1]) {
                        heap.remove();
                        heap.add(new int[]{key, value});
                    }
                } else {
                    heap.add(new int[]{key, value});
                }

            }
            for (int i = 0; i < k; i++) {
                res[i] = heap.peek()[0];
                heap.remove();
            }
            return res;
        }
    }

    // 快速排序
    class Solution {
        public int[] topKFrequent(int[] nums, int k) {
            Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
            for (int num : nums) {
                occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
            }

            List<int[]> values = new ArrayList<int[]>();
            for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
                int num = entry.getKey(), count = entry.getValue();
                values.add(new int[]{num, count});
            }
            int[] ret = new int[k];
            qsort(values, 0, values.size() - 1, ret, 0, k);
            return ret;
        }

        public void qsort(List<int[]> values, int start, int end, int[] ret, int retIndex, int k) {
            int pivot = values.get(end)[1];
            int i = start;
            for (int j = start; j < end; j++) {
                if (values.get(j)[1] > pivot) {
                    Collections.swap(values, j, i);
                    i++;
                }
            }
            Collections.swap(values, end, i);
            if (i - start + 1 == k) {
                for (int j = start; j <= i; j++) {
                    ret[retIndex++] = values.get(j)[0];
                }
            } else if (i - start + 1 > k) {
                qsort(values, start, i - 1, ret, retIndex, k);
            } else if (i - start + 1 < k) {
                for (int j = start; j <= i; j++) {
                    ret[retIndex++] = values.get(j)[0];
                }
                qsort(values, i + 1, end, ret, retIndex, k - (i - start + 1));
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}